package day02;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Jetwang
 * @version 1.0
 * @since 2023/3/2 14:11
 * 汉诺塔问题
 */
public class Hanoi {
    static LinkedList<Integer> a = new LinkedList<>();
    static LinkedList<Integer> b = new LinkedList<>();
    static LinkedList<Integer> c = new LinkedList<>();
    
    static void init(int n) {
        for (int i = n; i >= 1; i--) {
            a.addLast(i);
        }
    }

    /**
     * 汉诺塔问题
     * @param n 圆盘
     * @param a 源
     * @param b 借
     * @param c 目
     */
    static void move(int n, LinkedList<Integer> a,
                     LinkedList<Integer> b,
                     LinkedList<Integer> c) {
        if (n == 0) {
            return;
        }
        move(n-1, a, c, b); // 第一步
        c.addLast(a.removeLast()); // 中间一步
        print();
        move(n-1, b, a, c); // 第三步
    }

    public static void print() {
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
        System.out.println("======");
    }

    // 需要将n-1移到b 再将a的最后一块移动到c 最后将n-1从b移到c
    public static void main(String[] args) {
        init(3);
        print();
        move(3, a, b, c);
    }
}
